#pragma once
#include <cstdint>
#include <cstdlib>
#include <unordered_map>
#include <vector>
#include <fstream>
#include <iostream>
#include <climits>
#include <algorithm>
#include <numeric>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <cstring>
using namespace std;

#define MX_RECUR_DEPTH 0

#ifndef CHOICE
#define CHOICE 0
#endif

#if CHOICE == 0
    #define FILENAME "testmatrix.txt"
    #define OUTPUT_FILENAME "testmatrix"
    #define OPT 50

#endif



#define uint_t uint32_t 

clock_t global_st, global_en;
int global_mx_dr;
int ite_cnt;


typedef pair<int, int> pii;
typedef pair<uint, uint> puu;
typedef tuple<int, int, int, int> piiii;
typedef tuple<uint, uint, uint> tuuu;
typedef tuple<uint, uint, uint, uint> tuuuu;

int depth[17] = {-1, 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4}; 
#define d(x) depth[__builtin_popcount(x)]

string RANK = "_0_";

#define mx 5000
#define mxcst 300
typedef pair<int, int> pii;
typedef pair<uint_t, uint_t> puu;
typedef tuple<int, int, int> piii;
typedef tuple<int, int, int, int> tiiii;

int tot_time = 0;
int mx_depth = 0;

uint_t output[mxcst]{};
unordered_map<uint_t, int> index_output;
unordered_set<uint> extB[3];

tuple<uint, uint, uint> rule2[mx];
puu rule3[mx];
tuple<uint, uint, uint> rule4[mx];

int numInput, numTarget, numOutput;
int minm_cst;
int cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0, cnt5 = 0, cnt6 = 0, cnt7 = 0, cntrandom = 0;

void loop_init_state(vector<int> &s, int k);

bool loop_next_state(vector<int> &s, int k, int n);

void bp_with_target(vector<uint_t>& targets, vector<tuuu>& split, vector<int>& bound_ds);

void printbinary(uint_t x);
